package com.yangzhe.algorithm.c035;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 最大频率栈
public class Code06_MaximumFrequencyStack_LeetCode {
    /**
     * 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/
     * 不能用堆，因为堆结构不稳定
     */
    class FreqStack {

        /**
         * 将数字按频率分层存储，频率就是层数
         * key 是数字出现的频率，value是相同频率的数字的集合
         */
        private Map<Integer, List<Integer>> levelStack;

        /**
         * key 是数字，value是数字的皮女郎
         */
        private Map<Integer, Integer> valTimes;

        private int currentMaxLevel;

        public FreqStack() {
            levelStack = new HashMap<>();
            valTimes = new HashMap<>();
            currentMaxLevel = 0;
        }

        public void push(int val) {
            // 获取数字之前出现的次数
            Integer times = valTimes.get(val);
            if (times == null) {
                times = 0;
            }
            // 这次之后次数就 +1了
            int nextTimes = times + 1;

            // 将数字放入到对应层
            List<Integer> integers = levelStack.get(nextTimes);
            if (integers == null) {
                integers = new ArrayList<>();
            }

            integers.add(val);
            levelStack.put(nextTimes, integers);

            // 更新数字频率
            valTimes.put(val, nextTimes);

            if (nextTimes > currentMaxLevel) {
                currentMaxLevel = nextTimes;
            }
        }

        public int pop() {
            if (currentMaxLevel == 0) {
                return -1;
            }
            // 获取并pop出当前出现次数最多的数字
            List<Integer> integers = levelStack.get(currentMaxLevel);
            int result = integers.remove(integers.size() - 1);

            // 更新数字出现频率
            valTimes.put(result, valTimes.get(result) - 1);

            if (integers.isEmpty()) {
                // 如果当前层为空，则减一层
                levelStack.remove(currentMaxLevel);
                currentMaxLevel--;
            } else {
                // 如果当前层不为空，则更新当前层数字
                levelStack.put(currentMaxLevel, integers);
            }

            return result;
        }
    }

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(val);
 * int param_2 = obj.pop();
 */

}
